package com.ken.algorithms.tree;

import com.ken.algorithms.enums.NodeColor;

import java.util.Scanner;

/**
 * <ul>
 * <li>Title: RedBlackTree</li>
 * <li>Description: TODO </li>
 * </ul>
 *
 * @author swc
 * @date 2021-09-23 10:02
 */
public class RedBlackTreeTest {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入节点的数量");
        int nodeCount  = sc.nextInt();

        RedBlackTree root = null;
        for (int i = 0; i < nodeCount; i++) {
            System.out.println("请输入值");
            root = createTreeByParentNode(sc.nextInt(),root);
        }

        root.setColor(NodeColor.Black);

        //5 7 18 22 9
        System.out.println("----");
    }

    /**
     * 功能描述: 创建二叉树
     * @param value
     * @param parentNode
     * @return: algorithm.practice.Test.RedBlackTree
     * @author: 程序员ken
     * @date: 2021-08-26 10:22
     */
    private static RedBlackTree createTreeByParentNode(int value, RedBlackTree parentNode) {

        if(parentNode==null){
            parentNode = new RedBlackTree(value);
        }

        //当前值大于父节点 挂在右侧
        else if(parentNode.getVal()<value){
            //左右不平衡  防止变成斜树（链表）
            if(parentNode.getRight()!=null && parentNode.getLeft()==null){
                //左旋这棵树
                parentNode =leftRotationTree(value,parentNode);
            }
            //左右平衡
            else if(parentNode.getRight()!=null && parentNode.getLeft()!=null){
                createTreeByParentNode(value,parentNode.getRight());
            }
            else{
                parentNode.setColor(NodeColor.Red);
                parentNode.setRight(new RedBlackTree(value));
            }
        }else{
            //左右不平衡   防止变成斜树（链表）
            if(parentNode.getLeft()!=null && parentNode.getRight()==null){
                //右旋这棵树
                parentNode = rightRotationTree(value,parentNode);
            }
            //左右平衡
            else if(parentNode.getRight()!=null && parentNode.getLeft()!=null){
                createTreeByParentNode(value,parentNode.getLeft());
            }
            else{
                parentNode.setColor(NodeColor.Red);
                parentNode.setLeft(new RedBlackTree(value));
            }
        }

        //parentNode.setColor(NodeColor.Black);//根节点永远是黑色
        return  parentNode;
    }

    //左节点 右旋为父节点
    private static RedBlackTree rightRotationTree(int value, RedBlackTree parentNode) {
        RedBlackTree temp = parentNode.getLeft();
        parentNode.setLeft(null);
        temp.setRight(parentNode);//原父节点 变为左节点
        temp.setLeft(new RedBlackTree(value));//原父节点 变为左节点

        //父节点 颜色标记为红色
        temp.setColor(NodeColor.Red);
        //原父节点是否有子节点 没有节点变黑
        parentNode.setColor(parentNode.getLeft()==null&& parentNode.getRight()==null ?NodeColor.Black:NodeColor.Red);

        return temp;
    }

    //右节点 左旋为父节点
    private static RedBlackTree leftRotationTree(int value, RedBlackTree parentNode) {

        RedBlackTree temp = parentNode.getRight();
        parentNode.setRight(null);
        temp.setLeft(parentNode);//原父节点 变为左节点
        temp.setRight(new RedBlackTree(value));//原父节点 变为左节点

        //父节点 颜色标记为红色
        temp.setColor(NodeColor.Red);
        //原父节点是否有子节点 没有节点变黑
        parentNode.setColor(parentNode.getLeft()==null&& parentNode.getRight()==null ?NodeColor.Black:NodeColor.Red);

        return temp;
    }
}
